package com.zdp.剑指offer;


import com.zdp.util.ListNode;

public class 合并两个排序的链表 {
    public static void main(String[] args) {
        合并两个排序的链表 demo = new 合并两个排序的链表();
        ListNode orderList = ListUtil.createOrderList(15);
        ListUtil.outList(orderList);
        ListNode orderList1 = ListUtil.createOrderList(15);
        ListUtil.outList(orderList1);
        ListNode result = demo.Merge(orderList,orderList1);
        ListUtil.outList(result);
    }
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            if(list2==null)
                return null;
            else
                return list2;
        }
        if(list2==null){
            if(list1==null)
                return null;
            else
                return list1;
        }
        ListNode p1 = (list1.val<=list2.val)?list1:list2;
        ListNode p2 = (list1.val>list2.val)?list1:list2;
        ListNode pre = null;
        ListNode p = p1;
        while(p1!=null&&p2!=null){
            while(p1!=null&&(p2.val>=p1.val)){
                pre = p1;
                p1 = p1.next;
            }//插入
            ListNode p22 = p2.next;
            pre.next = p2;
            //注意到一个边界值 {1,2,3},{3,3,3}
            if(p1!=null){ //如果等于Null 还进行该操作的话，p2链表会被截断
                p2.next = p1;
                pre = p2;
                p2 = p22;
            }

        }
        return p;
    }
}
